package com.example.demo.search;

/**
 * 二分查找
 * 优点：比较次数少，查询速度快，平均性能好
 * 缺点：要求为有序表
 * 复杂度：
 * 最快：O(1)
 * 最坏：O(log2N)
 * 平均：
 */
public class BinarySearch {

    public static void main(String[] args) {
        int source[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
        System.out.println(doSearch(source, 81));
    }

    public static int doSearch(int[] nums, int target){
        int low = 0;
        int high = nums.length-1;
        while (low<=high){
            int mid = (high-low)/2 + low;
            int midNum = nums[mid];
            if(midNum==target){
                return mid;
            }else if(midNum>target){
                //左边
                high = mid - 1;
            }else{
                //右边
                low = mid + 1;
            }
        }
        return -1;
    }
}
